package bintree.LeetCode;

import java.util.*;

//前序遍历的非递归写法——借助栈


public class Num144_Solution_非递归 {
    public List<Integer> preorderTraversal(TreeNode root) {
           List<Integer> rep = new ArrayList<>();//创建一个数组来保存值
           if(root == null){
               return rep;//返回一个空数组
           }
           Deque<TreeNode> stack = new LinkedList<>();//创建一个栈
           stack.push(root);

           while(!stack.isEmpty()){
               TreeNode cur = stack.pop();//出栈
               rep.add(cur.val);
               //因为栈是先进后出，为了等会第一个弹出的是左子树，所以要反着入栈。
               if(cur.right != null){
                   stack.push(cur.right);
               }
               if(cur.left != null){
                   stack.push(cur.left);
               }
           }

        return rep;
    }
}
